package June;


import java.util.Scanner;
import java.util.TreeMap;

public class DAY0602 {
    //微信红包
    public int getValue(int[] gifts, int n) {
        // write code here
        //找红包金额次数超过总数一半的，返回所求金额的红包
        int m = 0;
        //用哈希表
        TreeMap<Integer,Integer> treeMap = new TreeMap<Integer,Integer>();
        for (int i = 0; i < n; i++) {
            if (n>1){
                if (treeMap.get(gifts[i])==null){
                    treeMap.put(gifts[i],1);
                }else {
                    int t = treeMap.get(gifts[i]).intValue();
                    t++;
                    if (t>n/2){
                        return m = gifts[i];
                    }
                    treeMap.put(gifts[i],t);
                }
            }
        }
        return m;
    }

    //计算字符串的编辑距离
    public static void main(String[] args) {
        //接收两个字符串
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            String s1 = scanner.next();
            String s2 = scanner.next();
            int n = numberOfOperations(s1,s2);
            System.out.println(n);
        }

    }

    private static int numberOfOperations(String s1, String s2) {
        int length1 = s1.length();
        int length2 = s2.length();

        //使用动态规划
        int[][] dp = new int[length1+1][length2+1];
        for (int i = 1; i <= length1; i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= length2; i++) {
            dp[0][i] = i;
        }

        for (int i = 1; i <= length1; i++) {
            for (int j = 1; j <= length2 ; j++) {
                //相等时
                if (s1.charAt(i-1)==s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }
                else {
                    dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                }
            }
        }

        return dp[length1][length2];
    }
}
